Repaso

• Gramática independiente del contexto (CFG).
• Lenguaje independiente del contexto.
• Gramática regular, lineal derecha, lineal izquierda.
• Derivación, derivación izquierda, derecha.
• Gramática ambigua.

Ejercicios

1. Describir los lenguajes generados por las siguientes gram?ticas:

   S → aA
   A → aA | bA | b
   

   S → aA
   A → aA | bB
   B → bB | ε

2. Para cada una de las siguientes gramáticas use notación de conjuntos para definir el leguaje que generan:

   S → aaSB | ε
   B → bB | b
   

   S → aSbb | A
   A → cA | c

3. Construya gramáticas independientes del contexto que generen cada uno de los siguientes lenguajes:

   {a^mbⁿ | m ≥ n}
   {aⁿb²ⁿc^m | n, m > 0}
   {w ∈ {a,b}^* | w tiene el doble de b que de a}

4. Construya autómatas de pila que reconozcan cada uno de los lenguajes en anteriores.

Definición Formal de Análisis Sintáctico (Parse)

Dada una gramática G, nos enfrentamos con dos problemas:

1. El problema de membresía: Dada una cadena w ∈ S^*^, ¿Pertenece w a L(G)?
2. El problema de derivación: Dada una cadena w ∈ L(G), encontrar una derivación para w.

Una Analizador Sintáctico es un algoritmo que se encarga de resolver uno o ambos problemas.

Los Autómatas Finitos resuelven el problema de membresía para los Lenguajes Regulares, y los Autómatas de Pila lo resuelven para los Lenguajes Independientes del Contexto.

Conocemos cómo implementar autómatas finitos de manera eficiente. Ahora estudiaremos cómo implementar autómatas de pila, y como resolver el problema de Derivacion.

Analizador Sintáctico

Dada una Gramatica Independiente del Contexto G=(Σ,N,P,S) y una frase de entrada w ∈ Σ^*, un Analizador Sintáctico (Parser) intenta encontrar una derivación (o un árbol de derivación) para la frase.

Análisis Sintáctico Descendente

Dada una gramática libre de contexto G=(Σ,N,P,S) y una frase de entrada w ∈ Σ^*, un Analizador Sintáctico Descendente (Top-Down Parser) intenta encontrar una derivación izquierda de la frase partiendo del símbolo no-terminal inicial S y reemplazando el no-terminal más a la izquierda por el lado derecho de una producción que tenga a ese no-terminal por lado izquierdo.

Configuración

Una configuración es una tupla que describe el estado de una máquina o procedimiento de análisis sintáctico en un momento dado. En el caso del Analisis Sintactico Descendente, dada una gramática G=(Σ,N,P,S), una configuración es una tupla:

⟨w$, Xα$, Π⟩

donde:

w ∈ Σ^*
Xα ∈ (Σ ∪ N)*, S ⇒^* a
Π=p ₁ p ₂ ... p _n | p _i∈ P

Y donde w es la parte de la cadena de entrada que queda por consumir, Xa es una forma sentencial obtenida mediante una derivación izquierda, y X es el símbolo más a la izquierda en dicha sentencia, y Π es la secuencia de producciones que produjeron dicha derivación. El símbolo $ es un nuevo símbolo que no está en S ni en N, y que usamos para denotar tanto el final de la secuencia de entrada como el de la forma sentencial.

Movimientos o Cómputos

Un movimiento (o cómputo) en una derivación es el paso de una configuración a otra, y se indica por el símbolo ├─. Los símbolos ├─ ^*, ├─ ⁺, y ├─ ^k tienen los significados usuales.

Derivaciones y Configuraciones

Con las configuraciones podemos describir de manera conveniente un proceso de derivación:

1. Si el símbolo más a la izquierda de la forma sentencial es un no-terminal, el mismo se substituye por la parte derecha de una de las producciones.
2. Si el símbolo más a la izquierda en la forma sentencial es un no-terminal distinto al primer símbolo en la entrada, se retrocede hasta la última sustitución de un no-terminal y se selecciona una producción distinta para hacer la sustitución. Si no hay más producciones que elegir, se aplica otro retroceso. Si es posible retroceder, la frase de entrada no pertenece al lenguaje
3. Cada vez que en una configuración el primer símbolo de la entrada coincide con el primer símbolo en la forma sentencial derivada hasta el momento, ambos símbolos se consumen.

Ejemplo

Dada la gramática

1. S → ( L )
2. L → A L
3. L → A
4. A → S
5. A → a

Hecho eso, podemos usar configuraciones para describir el proceso de análisis descendente de la frase de entrada: ((a)(a)a).

⟨((a)(a)a)$,S$,⟩	sustituir 1
├─⟨((a)(a)a)$,(L)$,1⟩	consumir (
├─⟨(a)(a)a)$,L)$,1⟩	sustituir 2
├─⟨(a)(a)a)$,AL)$,1 2⟩	sustituir 4
├─⟨(a)(a)a)$,SL)$,1 2 4⟩	sustituir 1
├─⟨(a)(a)a)$,(L)L)$,1 2 4 1⟩	consumir (
├─⟨a)(a)a)$,L)L)$,1 2 4 1⟩	sustituir 3
├─⟨a)(a)a)$,A)L)$,1 2 4 1 3⟩	sustituir 5
├─⟨a)(a)a)$,a)L)$,1 2 4 1 3 5⟩	consumir a
├─⟨)(a)a)$,)L)$,1 2 4 1 3 5⟩	consumir (
├─⟨(a)a)$,L)$,1 2 4 1 3 5⟩	sustituir 2
├─⟨(a)a)$,AL)$,1 2 4 1 3 5 2⟩	sustituir 4
├─⟨(a)a)$,SL)$,1 2 4 1 3 5 2 4⟩	sustituir 1
├─⟨(a)a)$,(L)L)$,1 2 4 1 3 5 2 4 1⟩	consumir (
├─⟨a)a)$,L)L)$,1 2 4 1 3 5 2 4 1⟩	sustituir 3
├─⟨a)a)$,A)L)$,1 2 4 1 3 5 2 4 1 3⟩	sustituir 5
├─⟨a)a)$,a)L)$,1 2 4 1 3 5 2 4 1 3 5⟩	consumir a
├─⟨)a)$,)L)$,1 2 4 1 3 5 2 4 1 3 5⟩	consumir )
├─⟨a)$,L)$,1 2 4 1 3 5 2 4 1 3 5⟩	sustituir 3
├─⟨a)$,A)$,1 2 4 1 3 5 2 4 1 3 5 3⟩	sustituir 4
├─⟨a)$,S)$,1 2 4 1 3 5 2 4 1 3 5 3 4⟩	sustituir 1
⟨a)$,(L)$,1 2 4 1 3 5 2 4 1 3 5 3 4 1⟩	retroceder 1
⟨a)$,S$,1 2 4 1 3 5 2 4 1 3 5 3 4⟩	retroceder 4
├─⟨a)$,A)$,1 2 4 1 3 5 2 4 1 3 5 3⟩	sustituir 5
├─⟨a)$,a)$,1 2 4 1 3 5 2 4 1 3 5 3 5⟩	consumir a
├─⟨)$,)$,1 2 4 1 3 5 2 4 1 3 5 3 5⟩	consumir )
├─⟨$,$,1 2 4 1 3 5 2 4 1 3 5 3 5⟩	fin

Como la derivación anterior demuestra, el análisis sintáctico descendente recursivo con retroceso (ASDRR) puede ser un proceso costoso incluso para gramáticas y frases de entrada sencillas. En particular, un ASDRR puede realizar una cantidad enorme de trabajo antes de darse cuenta que la decisión tomada en uno de los pasos iniciales fue equivocada.

Análisis Sintáctico Ascendente

Un Analizador Sintáctico Ascendente (Bottom-Up Parser) intenta encontrar una derivación derecha de la frase buscando lados derechos de producciones y reemplazándolos en cada paso por el no-terminal en el lado derecho correspondiente, hasta lograr una sustitución que produzca solo el símbolo inicial S.

El análisis ascendente consiste en partir desde una cadena buscando desde los elementos terminales (hojas) las producciones que generan esa cadena, intentando encontrar la raíz del árbol de derivación (axioma).

Ejemplo

Dada la gramática sobre el alfabeto que incluye paréntesis y la letra "a":

1. S → ( L )
2. L → L A
3. L → A
4. A → S
5. A → a

Un analizador sintáctico ascendente llevaría a cabo los siguientes pasos para encontrar una derviación de la frase ((a)(a)a):

⋅((a)(a)a)	shift
(⋅(a)(a)a)	shift
((⋅a)(a)a)	shift
((a⋅)(a)a)	reduce 5
((A⋅)(a)a)	reduce 3
((L⋅)(a)a)	shift
((L)⋅(a)a)	reduce 1
(S⋅(a)a)	reduce 4
(A⋅(a)a)	reduce 3
(L⋅(a)a)	shift
(L(⋅a)a)	shift
(L(a⋅)a)	reduce 5
(L(A⋅)a)	reduce 3
(L(L⋅)a)	shift
(L(L)⋅a)	reduce 1
(L S⋅a)	reduce 4
(L A⋅a)	reduce 2
(L⋅a)	shift
(La⋅)	reduce 5
(LA⋅)	reduce 2
(L⋅)	shift
(L)⋅	reduce 1
S⋅	end